package main

import (
	"fmt"
)

func main() {
	coins := []int{1, 2, 5, 10, 20, 50, 100}
	// f, s := getMinCoinsList(coins, 69)//计算较大值时，时间较长
	// fmt.Println(f, s)

	cacheFuncF1 := CacheFunc(coins)
	fmt.Println(cacheFuncF1(138))
}

/*
*	coins 硬币种类
*	final 总数
 */
func getMinCoinsList(coins []int, final int) (rArr []int, dep int) {
	if final == 0 {
		dep = 0
		return
	}
	if final < 0 {
		dep = -1
		return
	}

	for _, c := range coins {
		t, s := getMinCoinsList(coins, final-c)
		if s > -1 {
			if s < dep || dep == 0 {
				dep = s + 1
				rArr = append(t, c)
			}
		}
	}
	return rArr, dep
}

//闭包+递归+缓存
func CacheFunc(coins []int) func(int) ([]int, int) {
	mCache := struct {
		Dep map[int]int   //缓存深度值
		Arr map[int][]int //缓存组成金额最少的组合
	}{
		map[int]int{}, map[int][]int{},
	}

	var returnFunc func(int) ([]int, int)
	returnFunc = func(final int) (rArr []int, dep int) {
		if final == 0 {
			dep = 0
			return
		}
		if final < 0 {
			dep = -1
			return
		}

		for _, c := range coins {
			var t []int
			var s int
			query := final - c
			if r, ok := mCache.Arr[query]; ok {
				t = copyFuc(r) //此处复制切片;否则会导致append修改缓存中的数据
				s = mCache.Dep[query]
			} else {
				t, s = returnFunc(query)
				mCache.Dep[query] = s
				mCache.Arr[query] = t
			}

			if s > -1 {
				if s < dep-1 || dep == 0 {
					dep = s + 1
					rArr = append(t, c)
				}
			}
		}
		return rArr, dep
	}
	return returnFunc
}

func copyFuc(arr []int) (r []int) {
	r = make([]int, 0, len(arr))
	for _, v := range arr {
		r = append(r, v)
	}
	return
}
